package com.lwg.datastructure.commonSortingAlgorithm;

import java.util.Arrays;

/**
 * @author: lwg
 * @Date: 2022/4/21 12:05
 * @Description: 插入排序
 * 1. 一开始从第二个数进行遍历，然后与当前数前面的数进行比较，找到比它大的数，
 * 2. 下一个循环是将比它大的数往后移，最后将当前数放到合适的位置
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void insertSort(int[] arr) {
        // 从第二个数进行遍历
        for (int i = 1; i < arr.length; i++) {
            // 防止较大的数后移之后占据了当前数
            int key = arr[i];
            // 记录当前数可以放入的索引的位置
            int j = i;
            // 将当前数与其前面的数进行比较，大于当前数的往后挪
           /* for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > key) {
                    arr[j + 1] = arr[j];
                    // 用于比较所有的数之后再插入，避免比较一次插入一次
                    j--;
                }
            }*/
            while (j > 0 && arr[j - 1] > key) {
                arr[j] = arr[j - 1];
                j--;
            }
            //System.out.println("2==="+arr[i]);
            arr[j] = key;
        }
    }
}
